#include <vector>
class Solution
{
public:
    int ans = 0;

    vector<vector<int> > d = { {-1,0},{1,0},{0,-1},{0,1} };
    vector<int> find = { 0,0,0,0 };

    void dfs(int i, int j, vector<vector<char> >& grid)
    {
        if (i >= grid.size() || i < 0 || j >= grid[0].size() || j < 0 || grid[i][j] == '0')
        {
            return;
        }

        grid[i][j] = '0';

        for (int k = 0; k < d.size(); k++)
        {
            dfs(i + d[k][0], j + d[k][1], grid);
        }
    }

    int solve(vector<vector<char> >& grid)
    {
        for (int i = 0; i < grid.size(); i++)
            for (int j = 0; j < grid[0].size(); j++)
            {
                if (grid[i][j] == '1')
                {
                    ans++;
                    dfs(i, j, grid);
                }
            }

        return ans;
    }
};